package com.study.bloomFilter.myBloom;

import java.util.BitSet;

/**
 * 
 * @描述: 自己实现bloom过滤器
 * @版权: Copyright (c) 2020 
 * @公司: 
 * @作者: 严磊
 * @版本: 1.0 
 * @创建日期: 2020年5月30日 
 * @创建时间: 下午12:19:22
 */
public class MyBloomFilter
{
    /**
     * 位数组的大小
     */
    private static final int   DEFAULT_SIZE = 2 << 24;
    
    /**
     * 通过这个数组可以创建 6 个不同的哈希函数
     */
    private static final int[] SEEDS        = new int[] { 3, 13, 46, 71, 91, 134 };
    
    /**
     * 位数组。数组中的元素只能是 0 或者 1
     */
    private BitSet             bits         = new BitSet(DEFAULT_SIZE);
    
    /** 
     * 存放包含 hash 函数的类的数组
     */
    private SimpleHash[]       func         = new SimpleHash[SEEDS.length];
    
    /**
     * 
     * 描述：初始化多个包含 hash 函数的类的数组，每个类中的 hash 函数都不一样
     *     使用多个位数组，可以减少hash冲突带来的误判，必须是存在所有位数组中时，才判定这个元素存在
     */
    public MyBloomFilter()
    {
        // 初始化多个不同的 Hash 函数
        for (int i = 0; i < SEEDS.length; i++)
        {
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }
    
    /**
     * 
     * @描述：添加元素到位数组
     * @作者：严磊
     * @时间：2020年5月30日 下午12:00:56
     * @param value
     */
    public void add(Object value)
    {
        for (SimpleHash f : func)
        {
            bits.set(f.hash(value), true);
        }
    }
    
    /**
     * 判断指定元素是否存在于每一个位数组
     */
    public boolean contains(Object value)
    {
        boolean ret = true;
        for (SimpleHash f : func)
        {
            ret = ret && bits.get(f.hash(value));
            if(!ret)
            {
                return ret;
            }
        }
        return ret;
    }
    
    /**
     * 
     * @描述: 静态内部类。用于 hash 操作
     * @版权: Copyright (c) 2020 
     * @公司: 
     * @作者: 严磊
     * @版本: 1.0 
     * @创建日期: 2020年5月18日 
     * @创建时间: 上午11:58:23
     */
    public static class SimpleHash
    {
        
        private int cap;
        
        private int seed;
        
        public SimpleHash(int cap, int seed)
        {
            this.cap = cap;
            this.seed = seed;
        }
        
        /**
         * 
         * @描述： 计算 hash 值
         * @作者：严磊
         * @时间：2020年5月18日 上午11:58:32
         * @param value
         * @return
         */
        public int hash(Object value)
        {
            int h;
            return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }
        
    }
    
}
